#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustDown(int* arr, int n, int parents)
{
	//假设法：假设左孩子小
	int child = (parents * 2) + 1;
	//建小堆：谁小谁上去
	while (child < n)	//	child >= n 的时候说明超过了数组长度本身
	{
		if ((child + 1) < n && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[child] < arr[parents])
		{
			Swap(&(arr[child]), &(arr[parents]));
			parents = child;
			child = (parents * 2) + 1;
		}
		else
		{
			break;
		}
	}
}

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	//读取前k个元素
	int* HeapKmin = (int*)malloc(k * sizeof(int));
	if (HeapKmin == NULL)
	{
		perror("malloc fail!\n");
		exit(1);
	}
	for (int i = 0;i < k;i++)
	{
		fscanf(fout, "%d", &HeapKmin[i]);
	}

	//将前k个建小堆
	for (int i = (k - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(HeapKmin, k, i);
	}

	//读取后N-k个，依次比较交换向下调整
	int x = 0;
	while (fscanf(fout, "%d", &x) > 0)
	{
		if (x > HeapKmin[0])
		{
			HeapKmin[0] = x;
			AdjustDown(HeapKmin, k, 0);
		}
	}

	//打印
	for (int i = 0;i < k;i++)
	{
		printf("%d\n", HeapKmin[i]);
	}

	fclose(fout);
}

int main()
{
	int k = 0;
	printf("请输入k：");
	scanf("%d", &k);
	//CreateNDate();
	PrintTopK(k);
	return 0;
}